CF 1817A

我们称一个序列 $a_{1}, a_{2}, \dots, a_{n}$ 是好的，当且仅当不存在 $i$ （ $1 < i < n$ ）满足 $a_{i - 1} \geq a_{i} \geq a_{i + 1}$ 。

现给定一个序列 $a_{1}, a_{2}, \dots, a_{n}$ ，回答 $q$ 次询问，每次询问给出 $l$ 与 $r$ ，回答连续子序列 $a_{l}, a_{l + 1}, \dots, a_{r}$ 的最长的好的子序列的长度。

提示

正难则反，将如何获得最长的好的子序列转化为如何删去尽可能少的元素。

解答

考虑维护所有满足 $a_{i - 1} \geq a_{i} \geq a_{i + 1}$ 的元素的下标。只要它们不在每次询问的子序列的边界上，则必然不在最长的好的子序列中。随后通过前缀和进行计数，就可以在 $O (n + q)$ 的线性时间内解决问题。